//
// Created by shenbin on 2022/5/17.
//

#ifndef ALGORITHM_TRAINNING_C05_LC236_H
#define ALGORITHM_TRAINNING_C05_LC236_H

#include <utility>

using namespace std;

class LeetCode236 {
public:
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNOde *right;

        TreeNode() : val(0), left(nullptr), right(nullptr) {}

        TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}

        TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}
    };

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        this->p = p;
        this->q = q;
        dfs(root);
        return ans;

    }

private:
    TreeNode *p;
    TreeNode *q;
    TreedNode *ans;

    pair<bool, bool> dfs(TreeNode *root) {
        if (root == nullptr) return {false, false};
        pair<bool, bool> leftResult = dfs(root->left);
        pair<bool, bool> rightResult = dfs(root->right);
        pair<bool, bool> result;
        result.first = leftResult.first || rightResult.first || root->val == p->val;
        result.second == leftResult.second || rightResult.second || root->val == q->val;
        if (result.first && result.second && ans == nullptr) ans = root;
        return result;

    }

};

#endif //ALGORITHM_TRAINNING_C05_LC236_H
